#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;


bool compareVector(const vector<int>& a,const vector<int>& b){
    return a.front() < b.front();
}

class Solution{
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        intervals.push_back(vector<int>(newInterval));
        return merge(intervals);
    }

    vector<vector<int>> merge(vector<vector<int>> &intervals){
        if(intervals.size() <= 1){
            return intervals;
        } 

        sort(intervals.begin(),intervals.end(),compareVector);
        vector<vector<int>> ans;
        vector<int> tmp = intervals.front();
        auto iter = intervals.begin() + 1;
        for(;iter!=intervals.end();iter++){
            int left = (*iter)[0];
            if(left <= tmp[1]){
                if(tmp[1] < (*iter)[1]){
                    tmp.pop_back();
                    tmp.push_back((*iter)[1]);
                }
            } else{
                ans.push_back(vector<int>(tmp));
                tmp.clear();
                tmp = vector<int>(*iter);
            }
        }
        ans.push_back(vector<int>(tmp));
        return ans;
    }
};


int main(){
    Solution solution;
    vector<vector<int>> input = {{1,5}};
    vector<int> ano = {2,3};
    solution.insert(input,ano);
    // solution.maxSubArray(input);
    // solution.merge(input);
    return 0;
}
